1. Field of the Invention
The present invention relates to a sliced data structure used for a particle-based simulation based on a fluid calculation method using particles, which improves the memory efficiency for a method using a calculation grid used in a proximity search, and which improves the efficiency of a proximate particle search, and to a method for loading a particle-based simulation utilizing a sliced data structure into a GPU.
2. Description of the Related Art
The term “particle-based simulation” refers to a simulation method for performing calculations in which the physical object constituting the object of simulation is taken as a collection (aggregation) of numerous particles, and calculations are performed noting the individual behavior of the numerous particles. In calculations performed by a computer, “spheres” having a fixed diameter are ordinarily used as the abovementioned particles. In cases where the shape of the physical object is expressed by an aggregation of spheres, the degree of approximation or degree of spatial resolution of the physical object varies depending on the method used to determine the size (diameter) of these spheres. Furthermore, the degree of calculation precision and calculation speed in simulation calculations performed by a computer can be controlled by varying the diameter of the spheres, or varying the degree of spatial resolution.
In recent years, calculation of the behavior of fluids and the like has been performed utilizing the abovementioned particle-based simulation, and research on simulations of fluids and the like has been performed on the screens of computer display devices. Literature in which this research is disclosed includes Masayuki Tanaka et al., “Development of rigid body calculation method using particle method, and application to computer graphics,” Japan Society of Mechanical Engineers, Collection of Papers Presented at 19th Conference on Computational Power, pp. 701-702, 2006. Research on particle-based simulation techniques is important as a fundamental technique for computer graphics (CG).
Fluid simulation methods using the particle method include the MPS method (moving particle semi-implicit method) and SPH (smoothed particle hydrodynamics). In the MPS method, non-compressed flow is calculated by solving Poisson's equations derived from simultaneous equations; in SPH, quasi-non-compressed flow is calculated without setting non-compressed conditions. Accordingly, the MPS method has higher calculation costs than the SPH. Consequently, SPH methods constitute the mainstream in the field of computer graphics.
In the particle-based simulation research, mainly a method in which a calculation algorithm was prepared utilizing a CPU was widely used in the past. In recent years, however, research on particle-based simulations utilizing a GPU (graphic processing unit: generally a streaming processor) has also been underway. A GPU has a construction in which calculation processing is performed in parallel by a plurality of processors internally in order to make a special adaptation for graphics processing. Accordingly, in the case of processing of coordinate conversion of vertices and the like, a GPU can perform processing at a much higher speed than a CPU. Furthermore, a GPU can control processing by writing a program called a shader; accordingly, a GPU can also be used in various types of processing other than graphics. Accordingly, there have also been attempts to increase the speed of the calculations used in particle-based simulations using a GPU. For example, the inventors developed a method in which a GPU is used to perform all SPH simulations. Literature disclosing this method includes T. Harada, S. Koshizuka, and Y. Kawaguchi, Real-time Fluid Simulation Coupled with Cloth, Proc. Of Theory and Practice of Computer Graphics, 2007, and T. Harada, S. Koshizuka, and Y. Kawaguchi, Smoothed Particle Hydrodynamics on GPUs, Proc. Of Computer Graphics International, pages 63-70, 2007.
In the abovementioned method proposed by the present inventor, a grid fixed in space was used to search for proximate particles in particle-based simulations; accordingly, the following problems were encountered: namely, the memory efficiency was poor, and limitations were generated in regard to the calculation area.
For example, in fluid calculation methods using particles, unlike fluid calculation methods using a grid, a calculation grid is generally not used; accordingly, the following advantages are obtained: namely, fine droplets and the like can also be easily calculated, and the actual fluid behavior can be expressed. Meanwhile, in fluid calculation methods using grids, the disposition of the particles is altered dynamically without any connection between calculated particles; accordingly, processing that searches for particles present in the vicinity of certain coordinates is necessary in respective time steps in order to calculate physical quantities at such coordinates.
In order to perform a proximate particle search in an efficient manner, an increase in efficiency can be achieved by disposing a grid in the calculation area (calculation grid), and storing the numbers of certain particles in voxels (also called buckets or grids) containing these particles. Generally, calculation grids are prepared so that the calculation area is enveloped.
Generally, when a calculation grid is fixed and prepared in the above operation, there are many voxels in which particles are not present in cases where the particle distribution varies in the calculation area of a fluid, and the memory use efficiency is poor. There are limits to the size of memories in which simulation programs can be used; accordingly, as the size of the memory used in the calculation grid is reduced, the memory that can be used for particles that express the fluid increases, and a larger-scale fluid simulation can be performed.
Because of the abovementioned problems, there is a demand to increase the memory efficiency of the calculation grid used in the search for proximate particles in particle-based simulations.